/*
题目: 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
https://leetcode.cn/problems/generate-parentheses/
 */
public class GenerateParenthesis {
    List<String> result = new ArrayList<> ();

    public List<String> generateParenthesis(int n) {
        //分别定义左括号个数和右括号个数
        backTrack(n, n, new StringBuffer());
        return result;
    }

    private void backTrack(int left, int right, StringBuffer path) {
        if (left == 0 && right == 0) {
            result.add(path.toString());
            return;
        }

        if (left == right) { //如果剩下的左右括号一样多, 就只能先放左括号
            path.append("(");
            backTrack(left - 1, right, path);
            path.deleteCharAt(path.length() - 1);
        } else if (left < right) { //剩下的右括号比较多
            if (left > 0) {  //保证 left 的有效性
                path.append('(');  //那这时候加左加右都没问题
                backTrack(left - 1, right, path);
                path.deleteCharAt(path.length() - 1);
            }

            path.append(')');
            backTrack(left, right - 1, path);
            path.deleteCharAt(path.length() - 1);
        } //如果剩下的左括号比较多, 那就没救了
    }
}
